{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of All Subset XOR Totals"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array #math #backtracking #combinatorics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组 #数学 #回溯 #组合数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: subsetXORSum"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出所有子集的异或总和再求和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个数组的<strong> 异或总和</strong> 定义为数组中所有元素按位 <code>XOR</code> 的结果；如果数组为 <strong>空</strong> ，则异或总和为 <code>0</code> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如，数组 <code>[2,5,6]</code> 的 <strong>异或总和</strong> 为 <code>2 XOR 5 XOR 6 = 1</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你一个数组 <code>nums</code> ，请你求出 <code>nums</code> 中每个 <strong>子集</strong> 的 <strong>异或总和</strong> ，计算并返回这些值相加之 <strong>和</strong> 。</p>\n",
    "\n",
    "<p><strong>注意：</strong>在本题中，元素 <strong>相同</strong> 的不同子集应 <strong>多次</strong> 计数。</p>\n",
    "\n",
    "<p>数组 <code>a</code> 是数组 <code>b</code> 的一个 <strong>子集</strong> 的前提条件是：从 <code>b</code> 删除几个（也可能不删除）元素能够得到 <code>a</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [1,3]\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>[1,3] 共有 4 个子集：\n",
    "- 空子集的异或总和是 0 。\n",
    "- [1] 的异或总和为 1 。\n",
    "- [3] 的异或总和为 3 。\n",
    "- [1,3] 的异或总和为 1 XOR 3 = 2 。\n",
    "0 + 1 + 3 + 2 = 6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [5,1,6]\n",
    "<strong>输出：</strong>28\n",
    "<strong>解释：</strong>[5,1,6] 共有 8 个子集：\n",
    "- 空子集的异或总和是 0 。\n",
    "- [5] 的异或总和为 5 。\n",
    "- [1] 的异或总和为 1 。\n",
    "- [6] 的异或总和为 6 。\n",
    "- [5,1] 的异或总和为 5 XOR 1 = 4 。\n",
    "- [5,6] 的异或总和为 5 XOR 6 = 3 。\n",
    "- [1,6] 的异或总和为 1 XOR 6 = 7 。\n",
    "- [5,1,6] 的异或总和为 5 XOR 1 XOR 6 = 2 。\n",
    "0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>nums = [3,4,5,6,7,8]\n",
    "<strong>输出：</strong>480\n",
    "<strong>解释：</strong>每个子集的全部异或总和值之和为 480 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 12</code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 20</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-all-subset-xor-totals](https://leetcode.cn/problems/sum-of-all-subset-xor-totals/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-all-subset-xor-totals](https://leetcode.cn/problems/sum-of-all-subset-xor-totals/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,3]', '[5,1,6]', '[3,4,5,6,7,8]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res, n = 0, len(nums)\n",
    "        for x in nums:\n",
    "            res |= x\n",
    "        return res << (n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        for num in nums:\n",
    "            res |= num\n",
    "        return res << (n - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        return reduce(or_, nums) << (len(nums) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        def dfs(val, idx):\n",
    "            nonlocal res\n",
    "            if idx == n:\n",
    "                # 终止递归\n",
    "                res += val\n",
    "                return\n",
    "            # 考虑选择当前数字\n",
    "            dfs(val ^ nums[idx], idx + 1)\n",
    "            # 考虑不选择当前数字\n",
    "            dfs(val, idx + 1)\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        return sum(reduce(xor,l) for n in range(1,len(nums)+1) for l in combinations(nums,n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        def dfs(val, idx):\n",
    "            nonlocal res\n",
    "            if idx == n:\n",
    "                # 终止递归\n",
    "                res += val\n",
    "                return\n",
    "            # 考虑选择当前数字\n",
    "            dfs(val ^ nums[idx], idx + 1)\n",
    "            # 考虑不选择当前数字\n",
    "            dfs(val, idx + 1)\n",
    "        \n",
    "        dfs(0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        n = len(nums)\n",
    "        def dfs(val, idx):\n",
    "            nonlocal res\n",
    "            if idx == n:\n",
    "                # 终止递归\n",
    "                res += val\n",
    "                return\n",
    "            # 考虑选择当前数字\n",
    "            dfs (val ^ nums[idx], idx + 1)\n",
    "            # 考虑不选择当前数字\n",
    "            dfs(val, idx + 1)\n",
    "\n",
    "        dfs(0, 0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        candidates = [0]\n",
    "        for x in nums:\n",
    "            candidates += [x^y for y in candidates]  \n",
    "        return sum(candidates)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=0\n",
    "        temp=[]\n",
    "        mul=0\n",
    "        def backtrack(index):     \n",
    "            nonlocal ans,mul \n",
    "            for i in range(index,n):\n",
    "                temp.append(nums[i])\n",
    "                mul=mul^nums[i]\n",
    "                ans+=mul\n",
    "                backtrack(i+1)\n",
    "                temp.pop()\n",
    "                mul=mul^nums[i]\n",
    "        backtrack(0)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        # 二进制组合计算\n",
    "        before = [0]\n",
    "        res = 0\n",
    "        for i in range(len(nums)):\n",
    "            after = []\n",
    "            for record in before:\n",
    "                after.append(record)\n",
    "                tmp = record ^ nums[i]\n",
    "                res += tmp\n",
    "                after.append(tmp)\n",
    "            before = after\n",
    "        print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        s=sum(nums)\n",
    "        for i in range(2,len(nums)+1):\n",
    "            n=list(combinations(nums,i))\n",
    "            for x in n:\n",
    "                t=''\n",
    "                for y in x:\n",
    "                    t += str(y)\n",
    "                    t += '^'\n",
    "                t += '0'\n",
    "                s+=eval(t)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        all_jihe = self.get_sunset(nums)\n",
    "        all_sum = 0\n",
    "        for jihe in all_jihe:\n",
    "            all_sum += self.getXOR(jihe)\n",
    "        return all_sum\n",
    "\n",
    "    def getXOR(self, jihe: List[int]) -> int:\n",
    "        sum = 0\n",
    "        if len(jihe) == 0:\n",
    "            return 0\n",
    "        if len(jihe) == 1:\n",
    "            return jihe[0]\n",
    "        for num in jihe:\n",
    "            sum ^= num\n",
    "        return sum\n",
    "\n",
    "    def get_sunset(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        for num in nums:\n",
    "            res += [i + [num] for i in res]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        z = []\n",
    "        for i in range(1, len(nums)+1):\n",
    "            z.extend(combinations(nums,i))\n",
    "        z = [reduce(lambda x,y:x^y, i) for i in z]\n",
    "        return sum(z)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        all_l = []\n",
    "        sum_all = 0\n",
    "        for i in range(2 ** len(nums)):\n",
    "            new_l = []\n",
    "            for j in range(len(nums)):\n",
    "                if (i >> j) % 2 == 1:\n",
    "                    new_l.append(nums[j])\n",
    "            all_l.append(new_l)\n",
    "        for i in all_l[1:]:\n",
    "            res = 0\n",
    "            for j in range(len(i)):\n",
    "                res ^= i[j]\n",
    "            sum_all += res\n",
    "        return sum_all"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        def caucl(arr):\n",
    "            if not arr:\n",
    "                return 0\n",
    "            cur=arr[0]\n",
    "            for i in arr[1:]:\n",
    "                cur^=i\n",
    "            return cur\n",
    "        ans,path,n=[],[],len(nums)\n",
    "        def dfs(i):\n",
    "            ans.append(caucl(path))\n",
    "            for j in range(i,n):\n",
    "                path.append(nums[j])\n",
    "                dfs(j+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return sum(ans)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        n=len(nums)\n",
    "        ans=[]\n",
    "        temp=[]\n",
    "        def backtrack(index):       \n",
    "            for i in range(index,n):\n",
    "                temp.append(nums[i])\n",
    "                ans.append(reduce(lambda x,y:x^y,temp))\n",
    "                backtrack(i+1)\n",
    "                temp.pop()\n",
    "        backtrack(0)\n",
    "        return sum(ans)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        lst = [[]]\n",
    "        ans = 0\n",
    "        for n in nums:\n",
    "            s = []\n",
    "            for cur in lst:\n",
    "                s.append(cur + [n])\n",
    "            for d in s:\n",
    "                a = reduce(lambda x, y: x ^ y, d)\n",
    "                ans += a\n",
    "            lst += s\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        sub_list = [[]]\n",
    "        for num in nums:\n",
    "            for l in sub_list.copy():\n",
    "                l = l + [num]\n",
    "                sub_list.append(l)\n",
    "                res += functools.reduce(lambda x, y: x ^ y, l)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        def caucl(arr):\n",
    "            if not arr:\n",
    "                return 0\n",
    "            cur=arr[0]\n",
    "            for i in arr[1:]:\n",
    "                cur^=i\n",
    "            return cur\n",
    "        def huisu(n,k,startindex):\n",
    "            res.append(caucl(path.copy()))\n",
    "            for i in range(startindex,len(nums)):\n",
    "                path.append(nums[i])\n",
    "                huisu(nums,path,i+1)\n",
    "                path.pop()\n",
    "        res=[]\n",
    "        path=[]\n",
    "        huisu(nums,[],0)\n",
    "\n",
    "        return sum(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        ans=[]\n",
    "        seq=[]\n",
    "        self.walk(nums,seq,0,len(nums),ans)\n",
    "        s=0\n",
    "        for i in range(len(ans)):\n",
    "            if len(ans[i])!=0:\n",
    "                t=ans[i][0]\n",
    "                for j in range(1,len(ans[i])):\n",
    "                    t^=ans[i][j]\n",
    "            else:\n",
    "                t=0\n",
    "            s+=t\n",
    "        return s\n",
    "\n",
    "    def walk(self,nums,seq,cn,n,ans):\n",
    "        if cn>=n:\n",
    "            ans.append(seq)\n",
    "            return\n",
    "        self.walk(nums,seq.copy(),cn+1,n,ans)\n",
    "        seq.append(nums[cn])\n",
    "        self.walk(nums,seq,cn+1,n,ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        # 01 ^ 11  =   10\n",
    "        # 求子集\n",
    "        # 对子集进行异或\n",
    "        # 异或的过程重叠，可以进行优化\n",
    "\n",
    "        def dfs(nums, res, start, path):\n",
    "            res.append(path[:])\n",
    "            for i in range(start, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                dfs(nums, res, i+1, path)\n",
    "                path.pop()\n",
    "        res = 0\n",
    "        sub = []\n",
    "        dfs(nums, sub, 0, []) #求子集\n",
    "        print(sub)\n",
    "        for s in sub:\n",
    "            if s == []:\n",
    "                continue\n",
    "            t = s[0]\n",
    "            for i in range (1, len(s)):\n",
    "                t = s[i] ^ t\n",
    "            res += t\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        if len(nums) == 0:\n",
    "            return 0\n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        dic = dict()\n",
    "        def trackback(index: list):\n",
    "            nonlocal dic\n",
    "            if tuple(index) in dic:\n",
    "                ...\n",
    "            else :\n",
    "                temp = [i for i in index]\n",
    "                temp.pop(-1)\n",
    "                a = 0\n",
    "                for i in index:\n",
    "                    a ^= nums[i]\n",
    "                dic[tuple(index)] = a\n",
    "                \n",
    "            m = index[-1]\n",
    "            for i in range(max(index) + 1, len(nums) ):\n",
    "                temp = [j for j in index]\n",
    "                if max(temp) < len(nums):\n",
    "                    temp.append(i)\n",
    "                    trackback(temp)\n",
    "        for i in range(len(nums)):\n",
    "            trackback([i])\n",
    "        sumn = 0\n",
    "        for i, v in dic.items():\n",
    "            sumn += v\n",
    "        return sumn"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def f(i: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            for j in range(n-1, -1, -1):\n",
    "                if (1<<j)&i:\n",
    "                    return f(i^(1<<j))^nums[j]\n",
    "        return sum(f(i) for i in range(1<<n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        @cache\n",
    "        def f(i: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            for j in range(n):\n",
    "                if (1<<j)&i:\n",
    "                    return f(i^(1<<j))^nums[j]\n",
    "        return sum(f(i) for i in range(1<<n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        ret = []\n",
    "        def dfs(s, t):\n",
    "            nonlocal ret\n",
    "            if s > len(nums):\n",
    "                return\n",
    "            ret.append(list(t))\n",
    "            for i in range(s, len(nums)):\n",
    "                dfs(i + 1, t + [nums[i]])\n",
    "        dfs(0, [])\n",
    "        c = 0\n",
    "        for r in ret:\n",
    "            i = 0\n",
    "            for ri in r:\n",
    "                i ^= ri\n",
    "            c += i\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int: \n",
    "        sub_sets = []\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "        def backtrack(idx, sub_set):\n",
    "            sub_sets.append(sub_set)\n",
    "            if idx == n:\n",
    "                return None\n",
    "            else:\n",
    "                for i in range(idx, n):\n",
    "                    backtrack(i+1, sub_set + [nums[i]])\n",
    "        backtrack(0, [])\n",
    "\n",
    "        for set in sub_sets:\n",
    "            sum = 0\n",
    "            for i in set:\n",
    "                sum ^= i \n",
    "            res += sum \n",
    "        \n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        ans = []\n",
    "        cur = []\n",
    "        def backTracking(startIndex):\n",
    "            tmp = cur.copy()\n",
    "            if len(tmp) > 0:\n",
    "                ans.append(tmp)\n",
    "            #print(cur)\n",
    "            if startIndex >= len(nums):\n",
    "                return\n",
    "            for i in range(startIndex, len(nums)):\n",
    "                cur.append(nums[i])\n",
    "                backTracking(i + 1)\n",
    "                cur.pop()\n",
    "            return\n",
    "        \n",
    "        backTracking(0)\n",
    "        #print(ans)\n",
    "        res = 0\n",
    "        for i in range(len(ans)):\n",
    "            cur = 0\n",
    "            for j in range(len(ans[i])):\n",
    "                cur = cur ^ ans[i][j]\n",
    "            res += cur\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        def subsets(nums):\n",
    "            res = []\n",
    "            n = len(nums)\n",
    "            \n",
    "            def helper(i, tmp):\n",
    "                res.append(tmp)\n",
    "                for j in range(i, n):\n",
    "                    helper(j + 1,tmp + [nums[j]] )\n",
    "            helper(0, [])\n",
    "            return res\n",
    "        subSet = subsets(nums)\n",
    "        res = 0\n",
    "        for sub in subSet:\n",
    "            if(len(sub) == 0):\n",
    "                res += 0\n",
    "            else:\n",
    "                subRes = 0\n",
    "                for num in sub:\n",
    "                    subRes ^=num\n",
    "                res += subRes\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        self.sub=0\n",
    "        res=[]\n",
    "        def fun(i,tmp):\n",
    "            num=0\n",
    "            res.append(tmp)\n",
    "            for p in tmp:\n",
    "                num=num^p\n",
    "            self.sub=self.sub+num\n",
    "            for j in range(i,len(nums)):\n",
    "                fun(j+1,tmp+[nums[j]])\n",
    "        fun(0,[])\n",
    "        return self.sub"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        # O(2^n * n), O(n + 2^n * n)\n",
    "        def backtrack(idx):\n",
    "            # O(2^n),O(n + 2^n * n)\n",
    "            if idx == n:\n",
    "                subsets.append(tmp[:])\n",
    "                return\n",
    "            backtrack(idx + 1)\n",
    "            tmp.append(nums[idx])\n",
    "            backtrack(idx + 1)\n",
    "            tmp.pop()\n",
    "\n",
    "        n = len(nums)\n",
    "        subsets, tmp = [], []\n",
    "        backtrack(0)\n",
    "\n",
    "        res = 0\n",
    "        for subset in subsets:\n",
    "            xor_value = reduce(lambda x, y: x ^ y, subset) if subset else 0\n",
    "            res += xor_value\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        # 求出所有子集\n",
    "        # 所有子集求异或\n",
    "        # 求和\n",
    "        res = []\n",
    "        temp = []\n",
    "        n = len(nums)\n",
    "        def backtrace(index, k):\n",
    "            if len(temp) == k:\n",
    "                res.append(temp[:])\n",
    "            for i in range(index, n):\n",
    "                temp.append(nums[i])\n",
    "                backtrace(i+1, k)\n",
    "                temp.pop()\n",
    "        for i in range(n+1):\n",
    "            backtrace(0, i)\n",
    "        def xor(nums):\n",
    "            res = 0\n",
    "            n = len(nums)\n",
    "            if n == 0:\n",
    "                return 0\n",
    "            for i in range(n):\n",
    "                res = res ^ nums[i]\n",
    "            return res\n",
    "        result = 0\n",
    "        for item in res:\n",
    "            result += xor(item)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res, path = [], []\n",
    "        \n",
    "        l = len(nums)\n",
    "        def dfs(s, start, Sum):\n",
    "            nonlocal l\n",
    "\n",
    "            res.append(path[:])\n",
    "            #temp = 0\n",
    "            #for v in path:\n",
    "             #   temp = temp^v\n",
    "            #Sum += temp\n",
    "            if len(path)==l:return #Sum\n",
    "            for  i in range(start,l):\n",
    "                path.append(s[i])\n",
    "                #print(i, path)\n",
    "                dfs(s, i+1, Sum)\n",
    "                path.pop()\n",
    "\n",
    "        dfs(nums, 0, 0)\n",
    "        Sum = 0\n",
    "        for path in res:\n",
    "            temp = 0\n",
    "            for v in path:\n",
    "                temp = temp^v\n",
    "            Sum += temp\n",
    "        return Sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        def backtrack(start, k, temp, nums):\n",
    "            if k == 0:\n",
    "                ans.append(temp[:])\n",
    "                return\n",
    "            for i in range(start, n):\n",
    "                temp.append(nums[i])\n",
    "                backtrack(i + 1, k - 1, temp, nums)\n",
    "                temp.pop()\n",
    "\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        for i in range(n + 1):\n",
    "            backtrack(0, i, [], nums)\n",
    "        sum = 0\n",
    "\n",
    "        for i in ans:\n",
    "            e = 0\n",
    "            for j in i:\n",
    "                e ^= j\n",
    "            sum += e\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        def backtracing(nums,startIndex):\n",
    "            if startIndex >= n:\n",
    "                return\n",
    "            for i in range(startIndex,n):\n",
    "                path.append(nums[i])\n",
    "                res.append(path[:])\n",
    "                nonlocal ans\n",
    "                ans += reduce(lambda x,y:x^y,path,0)\n",
    "                backtracing(nums,i+1)\n",
    "                path.pop()\n",
    "        backtracing(nums,0)\n",
    "        return ans\n",
    "        \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        if not nums: \n",
    "            return 0\n",
    "        \n",
    "        if len(nums) == 1:\n",
    "            return nums[0]\n",
    "        \n",
    "        subsets = []\n",
    "        sums = []\n",
    "        results = 0\n",
    "\n",
    "        def dfs(nums, path):\n",
    "            subsets.append(path)\n",
    "            for i in range(len(nums)):\n",
    "                dfs(nums[i+1:], path + [nums[i]])\n",
    "\n",
    "        from functools import reduce\n",
    "        def getXORsums(subsets):\n",
    "            return reduce(lambda x, y: x ^ y, subsets) if subsets else 0\n",
    "        \n",
    "        dfs(nums, [])\n",
    "\n",
    "        return sum(map(getXORsums, subsets))\n",
    "            \n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        path = []\n",
    "        def backtrack(nums, start_idx):\n",
    "            res.append(path.copy())\n",
    "            \n",
    "            if start_idx == len(nums):\n",
    "                return\n",
    "            \n",
    "            for i in range(start_idx, len(nums)):\n",
    "                # if i > start_idx and nums[i - 1] == nums[i]:\n",
    "                #     continue\n",
    "                    \n",
    "                path.append(nums[i])\n",
    "                backtrack(nums, i + 1)\n",
    "                path.pop()\n",
    "                \n",
    "        backtrack(nums, 0)\n",
    "        \n",
    "        ans = 0\n",
    "        for r in res:\n",
    "            tmp = 0\n",
    "            if r is not None:\n",
    "                for n in r:\n",
    "                    tmp ^= n\n",
    "\n",
    "            ans += tmp\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        nums.sort()\n",
    "        res = []\n",
    "        def dfs(nums, path, start):\n",
    "            res.append(path[:])\n",
    "\n",
    "            for i in range(start, len(nums)):\n",
    "                path.append(nums[i])\n",
    "                dfs(nums, path, i+1)\n",
    "                path.pop()\n",
    "            \n",
    "        dfs(nums, [], 0)\n",
    "        ans = 0\n",
    "        for val in res:\n",
    "            ans += self.su(val)\n",
    "        return ans\n",
    "        \n",
    "    def su(self, num):\n",
    "        if len(num) == 0:\n",
    "            return 0\n",
    "        if len(num) == 1:\n",
    "            return num[0]\n",
    "        result = num[0]\n",
    "        for k in num[1:]:\n",
    "            result = result ^ k\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "        ans = 0\n",
    "        def backtracing(startIndex):\n",
    "            if startIndex >= n:\n",
    "                return\n",
    "            for i in range(startIndex,n):\n",
    "                path.append(nums[i])\n",
    "                res.append(path[:])\n",
    "                nonlocal ans\n",
    "                ans += reduce(lambda x,y:x^y,path,0)\n",
    "                backtracing(i+1)\n",
    "                path.pop()\n",
    "        backtracing(0)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        def solve(start,list_):\n",
    "            for i in range(start,n):\n",
    "                list_.append(nums[i])\n",
    "                res.append(list_.copy())\n",
    "                solve(i+1,list_)\n",
    "                list_.pop()\n",
    "        solve(0,[])\n",
    "        m = len(res)\n",
    "        ans = 0\n",
    "        print(res)\n",
    "        for i in range(m):\n",
    "            num = res[i][0]\n",
    "            k = len(res[i])\n",
    "            for j in range(1,k):\n",
    "                num ^= res[i][j]\n",
    "            ans += num\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        def dfs(index,li):\n",
    "            if li not in ans:\n",
    "                ans.append(li[:])\n",
    "                a = 0\n",
    "                if li:\n",
    "                    get = len(li)\n",
    "                    dp = [0]*get\n",
    "                    dp[0] = nums[li[0]]\n",
    "                    for j in range(1,get):\n",
    "                         dp[j] = dp[j-1]^nums[li[j]]\n",
    "                    a = dp[get-1]\n",
    "                arr[0] += a\n",
    "            if len(li) == n or index > n:\n",
    "                #print(f'len{li}=={n},返回操作')\n",
    "                return \n",
    "            for i in range(index,n):\n",
    "                if i in li or (li and li[-1] > i):\n",
    "                    #print(f'{i}在{li}{i in li} or{li}index指向从前{i}{li[-1] > i} 剪枝操作')\n",
    "                    continue\n",
    "                li.append(i)\n",
    "                #print(f'{li}添加{i} index+1:{index+1}')\n",
    "                dfs(index+1,li)\n",
    "                li.pop()\n",
    "                #print(f'撤销{m}')\n",
    "        ans = []\n",
    "        arr = [0]\n",
    "        n = len(nums)\n",
    "        dfs(0,[])\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        def dfs(index,li):\n",
    "            if li not in ans:\n",
    "                ans.append(li[:])\n",
    "                a = 0\n",
    "                if li:\n",
    "                    get = len(li)\n",
    "                    dp = [0]*get\n",
    "                    dp[0] = nums[li[0]]\n",
    "                    for j in range(1,get):\n",
    "                         dp[j] = dp[j-1]^nums[li[j]]\n",
    "                    a = dp[get-1]\n",
    "                arr[0] += a\n",
    "            if len(li) == n:\n",
    "                #print(f'len{li}=={n},返回操作')\n",
    "                return \n",
    "            for i in range(index,n):\n",
    "                if i in li or (li and li[-1] > i):\n",
    "                    #print(f'{i}在{li}{i in li} or{li}index指向从前{i}{li[-1] > i} 剪枝操作')\n",
    "                    continue\n",
    "                li.append(i)\n",
    "                #print(f'{li}添加{i} index+1:{index+1}')\n",
    "                dfs(index+1,li)\n",
    "                li.pop()\n",
    "                #print(f'撤销{m}')\n",
    "        ans = []\n",
    "        arr = [0]\n",
    "        n = len(nums)\n",
    "        dfs(0,[])\n",
    "        return arr[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        def backtrack(tmp,ind):\n",
    "            res.append(tmp[:])\n",
    "            for i in range(ind,len(nums)):\n",
    "                tmp.append(nums[i])\n",
    "                backtrack(tmp,i+1)\n",
    "                tmp.pop()          \n",
    "        res=[]\n",
    "        tmp=[]\n",
    "        ans=0\n",
    "        backtrack(tmp,0)\n",
    "        for lst in res:\n",
    "            if lst and len(lst)>1:\n",
    "                ans+=reduce(lambda x,y:x^y,lst)\n",
    "            elif lst:\n",
    "                ans+=lst[0]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        path = []\n",
    "\n",
    "        '''\n",
    "        i:起始下标\n",
    "        k:子集的长度，比如[5, 1, 6, 3]，其子集长度k=0，1，2，3，4，\n",
    "        '''\n",
    "\n",
    "        def bt(i, k):\n",
    "            if len(path) == k:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "\n",
    "            for j in range(i, n):\n",
    "                path.append(nums[j])\n",
    "                bt(j + 1, k)\n",
    "                path.pop()\n",
    "\n",
    "        def calc(x, y):\n",
    "            return x ^ y\n",
    "\n",
    "        for k in range(n + 1):\n",
    "            path = []\n",
    "            bt(0, k)\n",
    "        xor = 0\n",
    "        for r in res:\n",
    "            if len(r) == 0:\n",
    "                continue\n",
    "            elif len(r) == 1:\n",
    "                xor = xor + r[0]\n",
    "            else:\n",
    "                x = reduce(calc, r)\n",
    "                xor = xor + x\n",
    "        return xor\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        \"\"\"构建所有子集\"\"\"\n",
    "        res=[]\n",
    "        path=[]\n",
    "        def backtracking(cur,length):\n",
    "            # 判断是否最终状态\n",
    "            if len(path)==length:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            # 迭代列表递归\n",
    "            for i in range(cur,len(nums)):\n",
    "                path.append(nums[i])\n",
    "                backtracking(i+1,length)\n",
    "                path.pop()\n",
    "        # backtracking(0,2)\n",
    "        # print(res)\n",
    "        for i in range(1,len(nums)+1):\n",
    "            backtracking(0,i)\n",
    "        # print(res)\n",
    "        \"\"\"每个列表计算异或\"\"\"\n",
    "        sum=0\n",
    "        for li in res:\n",
    "            if len(li)==1:\n",
    "                sum+=li[0]\n",
    "            else:\n",
    "                cur_sum=0\n",
    "                for i in li:\n",
    "                    cur_sum^=i\n",
    "                sum+=cur_sum\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subsetXORSum(self, nums: List[int]) -> int:\n",
    "        \"\"\"构建所有子集\"\"\"\n",
    "        res=[]\n",
    "        path=[]\n",
    "        def backtracking(cur):\n",
    "            # 直接放入\n",
    "            res.append(path[:])\n",
    "            # 迭代列表递归\n",
    "            for i in range(cur,len(nums)):\n",
    "                path.append(nums[i])\n",
    "                backtracking(i+1)\n",
    "                path.pop()\n",
    "        backtracking(0)\n",
    "        \"\"\"每个列表计算异或\"\"\"\n",
    "        sum=0\n",
    "        for li in res:\n",
    "            if len(li)==1:\n",
    "                sum+=li[0]\n",
    "            else:\n",
    "                cur_sum=0\n",
    "                for i in li:\n",
    "                    cur_sum^=i\n",
    "                sum+=cur_sum\n",
    "        return sum"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
